/* Copyright 2017, 2018, 2019, 2020 Gabriel Czernikier
 *
 * This file is part of Côtehaus.
 * Côtehaus is free software: you can redistribute it and/or modify
 * it under the terms of one of the following:
 * 1. The same dual license as that of Côtehaus itself, of which individual licenses are
 * the MIT License and the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 2. The MIT License.
 * 3. The GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * Côtehaus is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * MIT License and the GNU General Public License for more details.
 * You should have received a copy of the MIT License and the GNU General Public License
 * along with Côtehaus.  If not, see <https://opensource.org/licenses/MIT> and <http://www.gnu.org/licenses/>.
 */
#define _BSD_SOURCE
#include <endian.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <wchar.h>
#include "composer.h"
#include "lgwseq.h"
#include "types.h"
#include "unresolved_type.h"

LIST_HEAD(unresolved_type_head);  // struct unresolved_type_st
LIST_HEAD(reftype_search_entry_head); /*struct search_entry_st : search_entry_type=REFTYPE*/
unsigned long reftype_search_entry_list_size = 0;
struct search_entry_st *oreftype_search_entry_ary; // sorted array from reftype_search_entry_head's elements.
LIST_HEAD(package_search_entry_head);  /*struct search_entry_st : search_entry_type=PACKAGE*/
unsigned int package_search_entry_list_size=0;
LIST_HEAD(search_context_stack);   // struct search_context_st* : the heads of search contexts
static search_context_stack_size;

// For types becoming resolved, at expenses of search_entry. List of search_entry_st collected in sough of becoming a type_id_st
// Instances are "java.lang" -> "String" giving rise to the type_id="java/lang/String", and "java.util" -> "Map" -> "Entry" giving rise to type_id="java/util/Map$Entry"
// struct schent_concat_for_typid_st is to a concatenation of just a few search_entry elements, together forming the complete name of a type_id (in Java's terms the fully qualified reference type), shortly lasting from upon a name is concatenated, but soon becoming droppable this list of entries as the concatenation merges in a long string so it becomes a type_id's str_dt (the reftype name of a type_id)
struct schent_concat_for_typid_st {
	struct search_entry_st *search_entry;  
	struct schent_concat_for_typid_st *next;
};

// Frees the memory of this object
void free_schent_concat_for_typid(struct schent_concat_for_typid_st *to_free) {
	// TODO
}

struct unresolved_type_st {
	struct token_list_st *RefTyp_group;
	struct list_head unresolved_type_list;
	struct list_head search_context_item_head;    // element type: struct search_context_item_st
	struct type_id_st **type_id_ptr_client;  // After type_id resolution who needs to know the latter blown type_id. There are the type_id's acquainters: proto_id_st.return_type, field_id_st."a_type_id", type_member_st.type_id, etc.
	wchar_t filename;
	struct CHLTYPE_st {
		int line, column;
	} loc;
};

void add_unresolved_type(struct token_list_st *RefTyp_group, struct list_head search_context_item_head, struct type_id_st **type_id_to_resolve) {
	struct unresolved_type_st *unresolved_type = malloc(sizeof(struct unresolved_type_st));
	unresolved_type->RefTyp_group = RefTyp_group;
	unresolved_type->search_context_item_head=search_context_item_head_ptr;
	unresolved_type->type_id_ptr_client=type_id_to_resolve;
	list_add(&unresolved_type->unresolved_type_list, &unresolved_type_head);
	unresolved_type_list_size++;
}

/* Adds a search_context_item onto the newest active context, possibly resulting in creating a new context for when no such context existed.
 * Design note: contexts shadow the newer the older, as grammatical context enclose one another. For instance "package a; import b; import c; class A { class B {}}".
 * Within '{' and '}' of "class B {}", context's stack is as follows:
 * There's a inutilized (bootstrap) context for "package a" and  "import"s. This shall not outlast (outlive) shadowing context, so estipulates pop_search_context.
 * There's a shadowed (older) context which items in order are: "class A" (search_entry), "package a" (search_entry), "import c" (Import_particles), "import b" (Import_particles).
 * And there's a shadowing (newer) context which items in order are: "class B" (search_entry), all items of the shadowed context.
 */
void add_search_context_item(struct token_list_st *Import_particles, struct search_entry_st * search_entry) {
	struct search_context_item_st *item = malloc(sizeof(struct search_context_item_st));
	// Retrieve current search_context from stack
	struct search_context_st *search_context;
	struct list_head *tmp=NULL;
	list_foreach(tmp, &search_context_stack)
		break;
	if(tmp==NULL) {
		search_context = malloc(sizeof struct search_context_st);
		list_add(&search_context->context_head_list, &search_context_stack);
	}
	else
		search_context = list_entry(tmp, struct search_context_st, context_head_list);
	
	list_add(&item->search_context, &search_context->context_head);
	if(Import_particles!=NULL) {
		item->search_context_item_entry.Import_particles = Import_particles;
		item->search_context_type = IMPORT;
	}
	else {  // search_entry!=NULL
		item->search_context_item_entry.search_entry=search_entry;
		item->search_context_type = ENTRY;
	}
	return search_context;
}

struct search_context_item_st *search_context_item_new(struct token_list_st *Import_particles, struct search_entry_st * search_entry) {
	struct search_context_item_st *item = malloc(sizeof(struct search_context_item_st));
	if(Import_particles!=NULL) {
		item->search_context_item_entry.Import_particles = Import_particles;
		item->search_context_type = IMPORT;
	}
	else {  // search_entry!=NULL
		item->search_context_item_entry.search_entry=search_entry;
		item->search_context_type = ENTRY;
	}
	return item;
}

void add_tail_search_context_item(struct token_list_st *Import_particles, struct search_entry_st * search_entry) {
	// TODO as the non-tail version but appending the list the opposite end.
}

/*
 * Pushes a new search_context and copies into it all of the search_context_items from the shadowed search_context.
 * Returns the newer context.
 */
struct search_context_st *push_search_context_copy() {
	// TODO (not so important): performance pursuit, instead of copying all the context items, make the new context to pin on the older.
	// Fetch the closest context.
	struct list_head *tmp;
	list_foreach(tmp, &search_context_stack)
		break;
	struct search_context_st *search_context = list_entry(tmp, struct search_context_st, context_head_list),
				 *search_context_copy = malloc(sizeof struct search_context_st);
	// Inserts a new, blank context in advance of it.
	list_add(&search_context_copy->context_head_list, &search_context_stack);
	LIST_HEAD_INIT(search_context_copy->context_head);
	// Fetches the items in the context.
	list_foreach(tmp, &search_context->context_head) {
		struct search_context_item_st *item = list_entry(tmp, struct search_context_item_st, search_context),
								*item_copy = malloc(sizeof(struct search_context_item_st));
		// Copies the items.
		item_copy->search_context_item_entry = item->search_context_item_entry;
		item_copy->search_context_type = item->search_context_type;
		// Add a new item to the new context, in the same order as items were in the outer context.
		list_add_tail(&item_copy->search_context, &search_context_copy->context_head);
	}
	search_context_stack++;
	return search_context_copy;
}

/* pop a search_context_st and returns it, which will permit iteration trhough one search_context_item or more,
	 being instances of items nearly sure to exist there: the import "java.lang.*", the declared package and the top level class thereunder. */
struct search_context_st *pop_search_context() {
	struct list_head *tmp;
	list_foreach(tmp, &search_context_stack) {
		list_del(tmp);
		if(--search_context_stack==0)  // void the stack by putting out the last item thereon, which is knowingly inutilized.
			list_del(tmp->next);
		return list_entry(tmp, struct search_context_st, context_head_list);
	}
}

struct search_context_st *peek_search_context() {
	// TODO return the context atop the stack.
}

// Compartisson only for osearch_entry_st which origin->search_entry_type==REFTYPE
int oreftype_search_entry_st_compar(struct *osearch_entry_st osearch_entry_1, struct *osearch_entry_st osearch_entry_2) {
	return lgwseq_t_compar(osearch_entry_1->origin->entry.unqualif_RefTyp,osearch_entry_2->origin->entry.unqualif_RefTyp);
}

/* Don't use it for package_search_entry_head. Its members are pointed at and accessed straightawayly; but never accessed in a search way.
 * Use it for reftype_search_entry_head. Faster access in a search way is of course of major interest.*/
void build_oreftype_search_entry(struct list_head *search_entry_head, int reftype_search_entry_list_size) {
	oreftype_search_entry_ary = malloc((reftype_search_entry_list_size)*sizeof(struct osearch_entry_st));
	//memset(oreftype_search_entry_ary, 0, (reftype_search_entry_list_size)*sizeof(struct osearch_entry_st));
	struct list_head *tmp;
	unsigned int i=0;
	list_for_each(tmp, &search_entry_head) {
		(oreftype_search_entry_ary+i)->origin = (struct search_entry_st *)list_entry(tmp, struct search_entry_st, search_entry_list);
		i++;
	}
	qsort(oreftype_search_entry_ary, reftype_search_entry_list_size, sizeof(struct osearch_entry_st), (int (*)(const void *, const void *))oreftype_search_entry_st_compar);
	struct osearch_entry_st *i, *j;
	for(i=oreftype_search_entry_ary; i<oreftype_search_entry_ary+reftype_search_entry_list_size; i=j) {
		for(j=i+1; j<oreftype_search_entry_ary+reftype_search_entry_list_size && !oreftype_search_entry_st_compar(i,j); j++) {
		j->equiv_class_representative = i;
		j->next_equiv_class = NULL;
		}
		i->equiv_class_representative = i;
		i->next_equiv_class = j<oreftype_search_entry_ary+reftype_search_entry_list_size?j:NULL;
	}
}

void resolve_types() {
	struct unresolved_type_st *unresolved_type;
	list_foreach_entry(unresolved_type, struct unresolved_type_st, unresolved_type_list, unresolved_type_head) {
		struct token_list_st *RefTyp_group = unresolved_type->RefTyp_group, *RefTyp_group_behind/*one less derivation than RefTyp_group*/;
		struct list_head *sctx;
		bool successful_match=false;
		list_foreach(sctx, &unresolved_type->search_context_item_head) {
			/* 1) reftyp_token=utmost_underived_reftyp_token(RefTyp_group) == search_entry_string and search_entry_type == "REFTYP" => follow; otherwise match fails
			 * str_dt = search_entry_string
			 * follow table:
			 * reftyp_token is derivable => reftype_token=derive(reftype_token), search_entry=search_entry.parent, goto 2
			 * otherwise => goto 4
			 */
			struct osearch_entry_st *osearch_entry = bsearch(RefTyp_group->token, oreftype_search_entry_ary, reftype_search_entry_list_size, sizeof(struct osearch_entry_st), (int (*)(const void *, const void *))key_oreftype_search_entry_st_compar),
				*other_class;
			if(osearch_entry==NULL)
				break;   // As for match fails in 1)
			struct search_entry *start_entry = osearch_entry->origin;
			for(osearch_entry = osearch_entry->equiv_class_representative, other_class=osearch_entry->next_class; osearch_entry!=other_class; osearch_entry++)
			{  //// search_entry_loop
				struct search_entry_st *search_entry=osearch_entry->origin;
				/* 2) reftyp_token == search_entry_string and search_entry_type == "REFTYP"  => follow; otherwise goto 3
				 * str_dt = search_entry_string + '$' + str_dt
				 * follow table:
				 * reftyp_token is derivable => reftype_token=derive(reftype_token), search_entry=search_entry.parent, goto 2
				 * otherwise => goto 4
				 */
				while(RefTyp_group!=NULL && search_entry!=NULL && search_entry->search_entry_type==REFTYPE && !lgwseq_t_compar(RefTyp_group->token, search_entry->entry.unqualif_RefTyp)) {
					RefTyp_group_behind = RefTyp_group;
					RefTyp_group = RefTyp_group->preceeding_token;
					search_entry = search_entry->parent;
				}
				if(RefTyp_group==NULL && search_entry==NULL) {
					// we are at default package
					successful_match = true;
					break;
				}
				if(RefTyp_group!=NULL) {
					/* 3) join('/', (reverse(recursive_derive(reftyp_token)) reftyp_token)) == search_entry_string and search_entry_type == "PACKAGE"  => match succeeds; otherwise match fails
					 * str_dt = search_entry_string + '/' + str_dt
 					 */
					if(search_entry!=NULL /*this exist to only standing for a default package was not reached*/
							&& search_entry->search_entry_type==PACKAGE && token_list_st_equals(search_entry->entry.pkg_particles, RefTyp_group)) {
						successful_match = true;
					}
					else {
						successful_match = false;
					}
				}
				else {
					// 4)
					struct search_context_item_st *sci = list_entry(sctx, struct search_context_item_st, search_context);	
					if(sci->search_context_type==IMPORT) {
						/* 4 [search_context_type="IMPORT"]) search_context_item_token=utmost_underived_import_token(ImportToken_group)==reftyp_token or search_context_item_token == '*'=> follow; otherwise match fails
						 * follow table:
						 * search_context_item_token == '*' => search_context_item_token=derive(search_context_item_token), search_entry=search_entry.parent, goto 6
						 * otherwise  => search_context_item_token=derive(search_context_item_token), search_entry=search_entry.parent, goto 5
						 */
						struct token_list_st *Import_particles = sci->search_context_item_entry.Import_particles;
						const lgwseq_t *WILDCARD;
						for_lgwseq(&WILDCARD, 1, L"*");
						if(lgwseq_t_compar(Import_particles->token, WILDCARD)) {
							if(lgwseq_t_compar(Import_particles->token, RefTyp_group_behind->reftype_token)) {
								// match fails for this search_entry and search_context_item
								successful_match = false;
								break;
							}
							// Go next to consumed Import_particles->token
							Import_particles = Import_particles->preceeding_token;
							/* 5) search_context_item_token == search_entry_string and search_entry_type == "REFTYP" and search_context_item_token is derivable  => follow; otherwise goto 6
							 * str_dt = search_entry_string + '$' + str_dt
							 * follow table: search_context_item_token=derive(search_context_item_token), search_entry=search_entry.parent, goto 5
							 */
							while(Import_particles!=NULL && search_entry!=NULL && search_entry->search_entry_type==REFTYPE && !lgwseq_t_compar(Import_particles->token, search_entry->entry.unqualifRefTyp) ) {
								Import_particles = Import_particles->preceeding_token;
								search_entry = search_entry->parent;
							}
							if(Import_particles!=NULL && search_entry!=NULL && search_entry.search_entry_type==PACKAGE && token_list_st_equals(Import_particles, search_entry->entry.pkg_particles)) {
								successful_match = true;
							}
							else if(Import_particles!=NULL || search_entry!=NULL) {
								// match fails for this search_entry and search_context_item
								successful_match = false;
							}
							else //This branch validates specifically about match success on a default package
								successful_match = true;
						}
						else {
							// Go next to "*"
							Import_particles = Import_particles/*"*"*/->preceeding_token;
							/* 6) join('/', (reverse(recursive_derive(search_context_item_token)) search_context_item_token)) == search_entry_string and search_entry_type == "PACKAGE" => match succeeds; otherwise match fails
							 * str_dt = search_entry_string + '/' + str_dt
							 */
							if(Import_particles!=NULL /*&& search_entry!=NULL // we know that because we reached here out from the earliest attemp to recognize a default package's presence*/ && search_entry.search_entry_type==PACKAGE && token_list_st_equals(Import_particles, search_entry->entry.pkg_particles)) {
								successful_match = true;
							}
							else if(Import_particles!=NULL) {
								// match fails for this search_entry and search_context_item
								successful_match = false;
							}
							else // A quirky case of matching with a default-package-based Import
								successful_match = true;

						}
						else {
							// match fails for this search_entry and search_context_item
							successful_match = false;
						}
					}
					else {
						/* 4 [search_context_type="ENTRY"]) search_context_item_entry==search_entry => match succeeds; match fails
						 *   str_dt = perlish_map( {search_entry_string + search_entry_type=="PACKAGE"?'/':'$'} recursive_topdown_parent_produce(search_entry)) + str_dt
						 */
						if(sci->search_context_item_entry->search_entry==search_entry) {
							successful_match = true;
						}
						else {
							// match fails for this search_entry and search_context_item
							successful_match = false;
						}
					}  // end 4 ENTRY)
				}  // end 4)
				if(successful_match)
					break;
			} //// osearch_entry loop
			if(successful_match)
				break;
		} // search_context_item loop
		if(successful_match) {
			*unresolved_type->type_id_ptr_client = start_entry->entry.reftype.type_id_target;
			// Restore unresolved_type loop invariant about ending the cycle with successful_match==false
			successful_match = false;
		}
		else  // Match failed.
			fprintf(stderr, "Unresolved type %s in file %s, at %d:%d.", RefTyp_str_produce(unresolved_type->RefTyp_group), unresolved_type->filename, unresolved_type->loc.line, unresolved_type->loc.column);
	}  // unresolved_type_loop
}
